"""
二分查找 Binary Search 是一种高效的查找算法 ,用于在有序数组中查找特定元素的位置,它的基本思想是通过
查找区间不断折半来缩小搜索范围,从而快速定位目标值

🧠 基本原理：
前提条件：数组必须是有序的（通常是升序或降序）。
初始化两个指针：
left 指向数组起始位置（通常为 0）
right 指向数组末尾位置（通常为 len(nums) - 1）
循环执行以下步骤直到 left > right：
计算中间索引：mid = left + (right - left) // 2
如果 nums[mid] == target，找到目标值，返回 mid
如果 nums[mid] < target，说明目标值在右半部分，更新 left = mid + 1
如果 nums[mid] > target，说明目标值在左半部分，更新 right = mid - 1
如果循环结束未找到目标值，返回 -1

二分查找的关键点
二分的关键就是st和ed两个指针如何移动,要注意的是 st只会往大的方向移动,ed只会往小方向移动
mid = st +(ed-st)/2 而不用 mid= (st+ed)/2 是因为后面的情况当st+ed很大时可能会产生溢出
注意避免死循环(一般就考虑最后两个数的极端情况)：
当mid = st + (ed-st)/2 时，mid偏向左边（一般求小于等于target的数），所以st必须移动st = mid+1，否则就可能会死循环。
当mid = st + (ed-st)/2 + 1，mid偏向右边（一般是求大于等于target的数），所以ed必须移动ed = mid -1，否则可能死循环

一般来说 如果求恰好找到的,可以多加一个等于的时候退出
有时候，我们不好判断到底判断条件里<还是<=的时候，可以把条件限定在2个数A，B（一般来说，此时的mid = A）和target：
A（mid） < target，我们需要st还是ed移动
A（mid） = target，我们需要st还是ed移动

一般问题
猜数问题 :这种题目一般是说找到里面特定的数字，这个数字是确定存在的，所以肯定会有一个一定匹配的问题,所以一般我们在判断条件中把if(r[mid] == target) 单独提出来
找位置 : 这类题目一般是说找到一个数它应该在数组中的位置，就是完整的套用框架。
找边界 :
这类题目有点麻烦，它需要用两次分别找左右边界。这里就需要考虑里面可能有和目标数相同的数。这时候就要特别注意是使用<=还是<，而在找右边界的时候，需要移动ed,这时候mid在原来的基础要+1


搜索范围
问题: 给定一个按照升序排列的整数数组，找出给定目标值的起始和结束位置。你的算法时间复杂度必须是 O (log n) 级别。如果数组中不存在目标值，则返回 [-1, -1] 。
nums = [5,7,7,8,8,10] target = 8

搜索范围是需要确定一个上确界,一个下确界
左边界 二分的话主要有以下几种情况 定义成3个基础规则
Rule 1. A[mid] < target ，这时候说明还可以向右，st = mid+1
Rule 2. A[mid] > target ， 这时候说明应该在左边，ed = mid-1
Rule 3. A[mid] == target ，这时候既可以左移，也可以不移动，ed = mid

因为作为二分，最后肯定是在2个数中选一个然后停止循环（while(st < ed)）。
考虑下面几种情况，假设 target=5：（在两个数的情况下mid = st）

case 1: [3 5] (A[st] = target > A[ed])
case 2: [5 7] (A[st] = target < A[ed])
case 3: [5 5] (A[st] = target = A[ed])
case 4: [3 7] (A[st] < target < A[ed])
case 5: [3 4] (A[st] < A[ed] < target)
case 6: [6 7] (target < A[st] < A[ed])

情况3就是rule1的情况 st = mid +1就行

✅ 解题思路：
我们分别实现两个函数：
find_left(nums, target)：寻找目标值的左边界
find_right(nums, target)：寻找目标值的右边界
🧠 左边界查找规则：
如果 nums[mid] < target，说明目标在右边，移动 left = mid + 1
如果 nums[mid] >= target，说明目标在左边或当前位置，移动 right = mid
🧠 右边界查找规则：
如果 nums[mid] > target，说明目标在左边，移动 right = mid - 1
如果 nums[mid] <= target，说明目标在右边或当前位置，移动 left = mid + 1


"""

class Solution:
    def search_range(self, nums, target):
        """
        在升序数组中找出目标值的起始和结束位置。

        参数:
            nums: List[int] - 升序排列的整数数组
            target: int - 要查找的目标值

        返回:
            List[int] - [起始位置, 结束位置]，若不存在则返回 [-1, -1]
        """
        # 定义一个内部函数，用于查找目标值的左边界
        def find_left():
            left, right = 0, len(nums) - 1
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            return left if nums[left] == target else -1

        # 定义一个内部函数，用于查找目标值的右边界
        def find_right():
            left, right = 0, len(nums) - 1
            while left < right:
                mid = left + (right - left + 1) // 2
                if nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid
            return left if nums[left] == target else -1

        # 如果数组为空，直接返回 [-1, -1]
        if not nums:
            return [-1, -1]

        # 调用 find_left() 函数找到目标值的左边界
        left_index = find_left()
        # 如果目标值不存在，直接返回 [-1, -1]
        if left_index == -1:
            return [-1, -1]

        # 调用 find_right() 函数找到目标值的右边界
        right_index = find_right()
        # 返回目标值的起始和结束位置
        return [left_index, right_index]



